BZOJ3295【CQOI2011】动态逆序对 < CDQ分治 >

Problem

【CQOI2011】动态逆序对

Description

对于序列，它的逆序对数定义为满足，且的数对的个数。
给到的一个排列，按照某种顺序依次删除个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数和，即初始元素的个数和删除的元素个数。
以下行每行包含一个到之间的正整数，即初始排列。
以下行每行一个正整数，依次为每次删除的元素。

Output

输出包含行，依次为删除每个元素之前，逆序对的个数。

Sample Input

Sample Output

HINT

标签：CDQ分治 树状数组 三维偏序

Solution

三维偏序，可上分治。

首先将删除操作离线，倒着做变成插入，并给每个数编号分别表示其下标、数值、插入时间。需要计算每个元素插入后会多出多少个逆序对，即对于三元组，有多少个满足或。
两个三维偏序，做两次分治后统计即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, pos[MAX_N+5], tr[MAX_N+5]; lnt ans[MAX_N+5];
struct node {int x, y, z, p, s;} a[MAX_N+5], b[MAX_N+5];
bool cmp1 (const node &a, const node &b) {return a.x < b.x;}
bool cmp2 (const node &a, const node &b) {return a.x > b.x;}
void inc(int p) {for (; p <= m+2; p += (p&-p)) tr[p]++;}
void dec(int p) {for (; p <= m+2; p += (p&-p)) tr[p]--;}
int sum(int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
void CDQ1(int s, int t) {
    if (s == t) return; CDQ1(s, mid), CDQ1(mid+1, t);
    for (int i = s, p1 = s, p2 = mid+1; i <= t; i++)
        b[i] = (p1 <= mid && (p2 > t || a[p1].y > a[p2].y)) ? a[p1++] : a[p2++];
    for (int i = s; i <= t; i++) a[i] = b[i];
    for (int i = s; i <= t; i++)
        if (a[i].x <= mid) inc(a[i].z+1);
        else a[i].s += sum(a[i].z+1);
    for (int i = s; i <= t; i++)
        if (a[i].x <= mid) dec(a[i].z+1);
}
void CDQ2(int s, int t) {
    if (s == t) return; CDQ2(s, mid), CDQ2(mid+1, t);
    for (int i = s, p1 = s, p2 = mid+1; i <= t; i++)
        b[i] = (p1 <= mid && (p2 > t || a[p1].y < a[p2].y)) ? a[p1++] : a[p2++];
    for (int i = s; i <= t; i++) a[i] = b[i];
    for (int i = s; i <= t; i++)
        if (a[i].x >= n-mid+1) inc(a[i].z+2);
        else a[i].s += sum(a[i].z+1);
    for (int i = s; i <= t; i++)
        if (a[i].x >= n-mid+1) dec(a[i].z+2);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        a[i].x = i, read(a[i].y), pos[a[i].y] = i;
    for (int i = m, x; i; i--) read(x), a[pos[x]].z = i;
    sort(a+1, a+n+1, cmp1); CDQ1(1, n);
    sort(a+1, a+n+1, cmp2); CDQ2(1, n);
    for (int i = 1; i <= n; i++) ans[a[i].z] += a[i].s;
    for (int i = 1; i <= m; i++) ans[i] += ans[i-1];
    for (int i = m; i; i--) printf("%lld\n", ans[i]); return 0;
}